\documentclass[a4paper, 12pt,TimesNewRoman]{article}
\usepackage[14pt]{extsizes}
\usepackage{cmap}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage[left=2cm,right=2cm,
top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\usepackage{indentfirst}
\usepackage{graphicx}
\graphicspath{{./images/}}
\usepackage {subcaption}
\usepackage{parskip}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage[unicode, pdftex]{hyperref}
\usepackage{float}
\author{Забродин Денис Александрович}
\title{\textbf{Группы}}

\begin{document}
	\maketitle
	\tableofcontents\newpage
	\section{Группы}
		\subsection{Нейтральный элемент}
			Пусть S - произвольное множество.
			Алгебраической операцией * на множестве S называется
			отображение *: ${S * S \rightarrow S}$
			
			Элемент e $\in$ S называется нейтральным элементом
			относительно операции *, если для каждого элемента a $\in$ S
			верно
			\[a * e = e * a = a\]
			
			\textbf{Утверждение 1}. Нейтральный элемент (если он существует)
			единственен.
			
			\textbf{Доказательство} проведем от обратного: пусть найдутся два
			нейтральных элемента e' $\in$ S и e'' $\in$ S, e' $\neq$ e''.
			Тогда
			\[e' * e''\]
			\[e' = e' * e'' = e''\]
		
		\subsection{Симметричный элемент}
			Для элемента a $\in$ S элемент a $\in$ S называется
			\textbf{симметричным}, если
			\[a * a' = a' * a = e,\]
			где e $\in$ S - нейтральный элемент относительно операции *.
			
			\textbf{Утверждение 2.} Симметричный элемент относительно
			ассоциативной операции (если он существует) единственен.
			
			\textbf{Доказательство} проведем от обратного: пусть для некоторого
			элемента a $\in$ S найдутся два симметричных элемента a' $\in$ S и
			a'' $\in$ S, a' $\neq$ a''.
			Тогда
			\[a' * a * a''\]
			\[a' = a' * e = a' * (a * a'') = (a' * a) * a'' = e * a'' = a''\]
			
		\subsection{Группа}
			Множество S с одной или несколькими введенными на нем
			операциями называется алгебраической структурой.
			Структура G = (S; *) (т. е. множество S с введенной на нем
			алгебраической операцией *) называется группой, если
			\begin{enumerate}
				\item операция * ассоциативна, т. е. для любых элементов
				a, b, c $\in$ S верно
				\[(a * b) * c = a * (b * c)\]
				\item cуществует нейтральный элемент относительно операции *,
				т. е. найдется такой элемент e $\in$ S, что для каждого элемента
				a $\in$ S верно
				\[a * e = e * a = a\]
				\item для каждого элемента a $\in$ S найдется симметричный к нему
				элемент a' $\in$ S, т. е. такой что
				\[a * a' = a' * a = e)\]
			\end{enumerate}
			Если для группы G = (S; *) дополнительно выполнено, что
			операция * коммутативна, т. е. для любых элементов
			a, b $\in$ S верно
			\[a * b = b * a\]
			то такая группа называется \textbf{коммутативной}, или \textbf{абелевой}.
			
			\hypertarget{1}{\textbf{Утверждение 3} (правило сокращения)}.
			Пусть G = (S; *) - группа. Тогда если для некоторых
			элементов a, b, c $\in$ G верно
			
			a * b = a * c (или b * a = c * a), то b = c
			
			\textbf{Доказательство}. Пусть элемент a' $\in$ G симметричен
			относительно операции * к элементу a $\in$ G . Элемент a' $\in$ G
			найдется, т. к. G – группа. Тогда
			\[a * b = a * c\]
			\[a' * a * b = a' * a * c\]
			\[b = e * b = (a' * a) * b = (a' * a) * c = e * c = c\]
			
			\textbf{Утверждение 4}. Таблица умножения конечной группы - это латинский квадрат. Напомню: латинский квадрат - это таблица чисел, в каждой строке и в каждом столбце которой записаны все элементы группы.
			
			\textbf{Доказательство}. Обозначим элементы группы через $a_{1}, a_{2}, \dots, a_{n}$.
			Какие элементы записаны в n-oм столбце? Те, что определяются умножением $a_{n} * a_{1}, a_{n} * a_{2}, a_{n} * a_{3}, \dots, a_{n} * a_{n}$. Допустим, что два выражения из этого списка равны, то есть существуют два индекса j и k такие, что $a_{n} * a_{i} = a_{n} * a_{k}$. Так как $a_{n}$ приводится в обеих частях выражения, по закону \hyperlink{1}{сокращения} имеем $a_{j} = a_{k}$. Таким образом, в этом столбце нет двух одинаковых элементов! Но так как группа состоит из n элементов, а в столбце таблицы нужно записать n неповторяющихся элементов, то в этом столбце будут записаны все элементы группы
			
		\subsection{Порядок группы и элемента}
			Группа G = (S; *) называется \textbf{конечной}, если в множестве S
			конечное число элементов.
			Если группа G = (S; *) конечна, то число элементов в
			множестве S называется ее \textbf{порядком} и обозначается |G|
			
			Пусть G = (S; *) - группа с нейтральным элементом e.
			Для элемента a $\in$ G наименьшее натуральное число n (если
			оно существует), такое что
			\[\underbrace{a * a * \dots * a}_{n} = e\],
			называется его \textbf{порядком}\newline
			Вам может показаться, что это определение не имеет ничего общего с предыдущим, но это не так.
			
			Рассмотрим произвольный элемент группы, например a. Мы можем составить группу степеней a, то есть <a> = {$a, a^{2}, a^{3} \dots$}. Допустим, что a имеет порядок n в соответствии со вторым определением, то есть $a^{n}$ - нейтральный элемент. Тогда перечень степеней остановиться на $a^{n}$ = e и затем начнется сначала. Множество будет содержать всего n элементов. И это непростое множество: <a>, в свою очередь, является группой: оно содержит нейтральный элемент, результат операции над двумя степенями a всегда равен степени a, и элемент $a^{n-i}$ является обратным для $a^{i}$. Следовательно, порядок элемента - это порядок множества, состоящего из его степеней
%		\subsection{Конечные коммутативные группы}
%			\textbf{Утверждение 4.} Пусть G = (S; *) - конечная коммутативная группа и e $\in$ S - 
%			нейтральный элемент. Тогда для любого
%			элемента a $\in$ S верно $\underbrace{a * . . . * a}_{|G|} = a^{|G|} = e$.
%			
%			\textbf{Доказательство}. Пусть S = {$a_{1}$,\dots , $a_{n}$}, и a $\in$ S. Рассмотрим
%			элементы группы
%			\[a \cdot a^{}_{1}, a \cdot a^{}_{2} \dots a \cdot a^{}_{n}\]
%
%			Все эти элементы различны. И их ровно n. Значит,
%			здесь перечислены все элементы группы.
%			Поэтому, с учетом коммутативности и ассоциативности
%			операции *, получаем:
%			\[\prod_{i=1}^{n}a_{i} = \prod_{i=1}^{n}(a * a_{i}) = a^{|G|}\prod_{i=1}^{n}a_{i}\]
%			По правилу сокращения получаем $a^{|G|} = e$.
		\subsection{Малая теорема Ферма}
			\centering $\forall$ простого p;
			$\forall$ a $\in$ $\mathbb{Z}$
			\[a^{p} - a \mid p\] или
			
			\centering $\forall$ просто p; $\forall$ a $\nmid$ p
			\[a^{p-1} - 1 \mid p\]
			
			\raggedright \textbf{Лемма:} Для любого простого числа p и целого числа k, не кратного p, произведения k и чисел 1, 2, 3, \dots, p-1 при делении на p в остатке дают те же самые числа 1, 2, 3, \dots, p-1, возможно, записанные в некотором другом порядке.
			
			\textbf{Доказательство леммы:} Произведение k и любого из чисел 1, 2, 3, \dots, p-1 не кратно, следовательно, в остатке не может получиться 0. Все остатки разные. Докажем последнее утверждение от противного. Пусть при $a, b \in {1, 2, 3, \dots, p-1}$ и $a \neq b$ два произведения ak и bk дают при делении на p одинаковые остатки, тогда разность $ak - bk = (a - b)k$ кратна p, что невозможно, поскольку a - b не кратно p. Всего существует p - 1 различных ненулевых остатков от деления на p. 
			
			\textbf{Доказательство:}
			Пусть \{1, 2, \dots, p-1\} - ненулевые остатки от деления на p, тогда согласно вышеприведённой лемме остатки от деления чисел $a, 2a, 3a, \dots, (p-1)a$ - это с точностью до перестановки числа \{1, 2, \dots, p-1\}, то $a * 2a * 3a, \dots, (p-1)*a \equiv 1*2*3*\dots*(p-1) (mod\ p)$. Отсюда $a^{p-1}(p-1)! \equiv (p-1)! (mod\ p)$. Последнее соотношение можно сократить на (p-1)!, поскольку все сомножители являются числами, взаимно простыми с основанием p, в результате получаем требуемое утверждение $a^{p-1} \equiv 1 (mod\ p)$
			
			\textbf{Доказательство 2:} $(a + b)^{p}$ = $a^{p}$ + $C^{1}_{p}a^{p-1}b$ + $C^{2}_{p}a^{p-2}b$ + \dots + $C^{p-1}_{p}$ + $b^{p}$
			
			$C^{k}_{p}$ = $\frac{p!}{k!(p-k)!}$ = $\frac{p(p-1)!}{k!(p-k)!}$, тк $C^{k}_{p} \in \mathbb{Z}$, то и
			$\frac{p(p-1)!}{k!(p-k)!} \in \mathbb{Z}$
			
			k $\in$ \{1, 2, 3, \dots, p-1\} $\Rightarrow$ p $\nmid$ $k!(p-k)!$ $\Rightarrow$ $(p-1)! \mid k!(p-k)!$
			
			$\frac{(p-1)!}{k!(p-k)!} = l \in \mathbb{Z}$ $\Rightarrow$ $C^{k}_{p} = pl$ $\Rightarrow$ $C^{k}_{p} \mid p$
			
			$(a + b)^{p}$ $\equiv$ $a^p + b^p$ (mod p)
			
			\underline{\textbf{Дальнейшие вычисления происходят по модулю p}}
			
			$(1 + 1)^{p} \equiv 1^{p} + 1^{p} \equiv 2 \equiv 2^{p}$
			
			$(2 + 1)^{p} \equiv 2^{p} + 1^{p} \equiv 2 + 1 \equiv 3 \equiv 3^{p}$
			
			$k \in \mathbb{N}$
			\textbf{База:} Пусть верно, что $(k + 1)^{p} \equiv k^{p} + 1^{p} \equiv k + 1$
			
			\textbf{Переход:} Докажем для k + 1
			
			$((k + 1) + 1)^{p} \equiv (k + 1)^{p} + 1^{p}$, тк $(k + 1)^{p} \equiv k + 1$, то $(k + 1)^{p} + 1^{p} \equiv k + 1 + 1 \equiv k + 2 \equiv (k + 2)^{p}$ чтд
			
			Для k < 0 доказывается аналогично $\Rightarrow$ k $\in$ $\mathbb{Z}$ $\Rightarrow$ Выражение $a^n \equiv a$ верно для a $\in$ $\mathbb{Z}$
			
			\textbf{Замечание}: Для k = 0 можно проверить руками\\
			Для p = 2 и k < 0:\newline
			$(-k + 1)^{2} \equiv (-k)^{2} - 2k + 1^{p} \equiv (-k)^{2} + 1^{p}$		
\end{document}